package StackandQueue;

import java.util.*;

public class MaxNumInSlidingWindow {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        MaxNumInSlidingWindow solution = new MaxNumInSlidingWindow();
        int[] result = solution.maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(result));
    }

    public int[] maxSlidingWindow(int[] nums, int k){

//        Collection<Integer> collection = new LinkedList<Integer>();

        if(nums == null || nums.length < 2) return nums;
        //双向队列，但是后面实际上是实现了单调递减队列，让队列的头元素一直是最大的元素
        //其次就是保存的是当前窗口最大值的数组下标，这样做的好处是
        Deque<Integer> queue = new LinkedList<>();
        //结果数组
        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length; i++){
            //该元素与队列尾部元素比较，如果该元素大，则一直将队尾移除。保持队列头部元素是最大的元素，实现单调
            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
                queue.pollLast();
            }
            //加入元素下标
            queue.addLast(i);
            //每次移动之后（进入for循环之后），要判断队首的值还在不在滑动窗口里，不在的话要移除
            //这里的i + 1 - k实际上就是窗口闭区间[R,L]中的R，超出边界显然就要移除
            if(queue.peek() < i + 1 - k){
                queue.pollFirst();
            }
            //此时滑动窗口长度达到k，记录当前窗口最大值
            if(i + 1 >= k){
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }

    public int[] maxSlidingWindow2(int[] nums, int k){
        if(nums == null || nums.length < 2) return nums;
        //双向队列，但是后面实际上是实现了单调递减队列，让队列的头元素一直是最大的元素
        //这里队列存放的是最大值
        Deque<Integer> queue = new LinkedList<>();
        //结果数组
        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length; i++){
            //该元素与队列尾部元素比较，如果该元素大，则一直将队尾移除。保持队列头部元素是最大的元素，实现单调
            while(nums[i] > queue.peekLast()){
                queue.pollLast();
            }
            //加入元素值
            queue.addLast(nums[i]);
            //每次移动之后（进入for循环之后），要判断队首的值还在不在滑动窗口里，不在的话要移除
            if(queue.peek() <= i - k){
                queue.pollFirst();
            }
            //此时滑动窗口长度达到k，记录当前窗口最大值
            if(i + 1 >= k){
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }
}
